#include <iostream>
#include <vector>
#include <string>
#include <climits>

using namespace std;

// https://leetcode.cn/problems/maximum-difference-between-even-and-odd-frequency-ii/description/?envType=daily-question&envId=2025-06-11
// 3445. 奇偶频次间的最大差值 II

class Solution1
{
public:
    int maxDifference1(string s)
    {
        vector<int> countOfChar(5);
        for (int i = 0; i < s.size(); i++)
        {
            int curIndex = s[i] - '0';
            ++countOfChar[curIndex];
        }
        int maxOdd = 0;
        int minEven = INT_MAX;
        for (auto it : countOfChar)
        {
            if (it != 0)
            {
                if (it % 2 == 0)
                {
                    minEven = min(minEven, it);
                }
                else
                {
                    maxOdd = max(maxOdd, it);
                }
            }
        }
        return maxOdd - minEven;
    }
    int maxDifference(string s, int k)
    {
        int ans = INT_MIN;
        for (int j = 0; j <= s.size() - k; j++)
        {
            string target(s.begin() + j, s.begin() + j + k);
            ans = max(maxDifference1(target), ans);
            for (int i = k + j; i < s.size(); i++)
            {
                target += s[i];
                ans = max(maxDifference1(target), ans);
            }
        }

        return ans;
    }
};

class Solution
{
public:
    int maxDifference(string s, int k)
    {
        int n = s.size();
        int ans = INT_MIN;
        vector<vector<int>> sumNum(n, vector<int>(5));
        for (int i = 0; i < n; i++)
        {
            if (i > 0)
            {
                sumNum[i] = sumNum[i - 1]; // copy previous counts
            }
            ++sumNum[i][s[i] - '0'];
        }
        for (int x = 0; x < 5; x++)
        {
            for (int y = 0; y < 5; y++)
            {
                if (x == y)
                {
                    continue;
                }
                for (int begin = 0; begin < n - k; begin++)
                {
                    for (int end = begin + k - 1; end < n; end++)
                    {
                        int xSum = 0;
                        int ySum = 0;
                        if (begin == 0)
                        {
                            xSum = sumNum[end][x];
                            ySum = sumNum[end][y];
                        }
                        else
                        {
                            xSum = sumNum[end][x] - sumNum[begin - 1][x];
                            ySum = sumNum[end][y] - sumNum[begin - 1][y];
                        }
                        if ((xSum % 2) == (ySum % 2))
                            continue;
                        if (xSum % 2 == 0)
                        {
                            ans = max(ySum - xSum, ans);
                        }
                        else
                        {
                            ans = max(xSum - ySum, ans);
                        }
                    }
                }
            }
        }
        return (ans == INT_MIN) ? -1 : ans;
    }
};

int main()
{
    return 0;
}